package com.base.dynamicprograming;

import java.util.LinkedList;

/**
 * 1567. 乘积为正数的最长子数组长度
 * 给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。
 * <p>
 * 一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。
 * <p>
 * 请你返回乘积为正数的最长子数组长度。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximum-length-of-subarray-with-positive-product
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author leon
 * @date 2021年12月01日 21:40
 */
public class MaxSubarrayProductLen {
    /**
     * 滑动窗口
     *
     * @param nums
     * @return
     */
    public int getMaxLen(int[] nums) {
        int max = 0, negative = 0;
        int left = -1, right = 0;
        //保存第一个负数的位置，和最后一个零的位置
        int[] savePosition = new int[2];
        for (; right < nums.length; right++) {
            // 当遇到零时，计算正的长度
            if (nums[right] == 0) {

                if (negative % 2 == 0) {
                    max = Math.max(max, right - left-1);
                } else {
                    max = Math.max(max, Math.max(savePosition[1] - left-1, right - savePosition[0] - 1));
                }
                left = right;
                negative = 0;
                savePosition[0] = savePosition[1] = right;


            } else if (nums[right] < 0) {
                if (negative == 0) {
                    savePosition[0] = right;
                }
                savePosition[1] = right;
                negative++;
            }
        }
        if (negative % 2 == 0) {
            max = Math.max(max, right - left-1);
        } else {
            max = Math.max(max, Math.max(savePosition[1] - left, right - savePosition[0] - 1));
        }
        return max;
    }

    public static void main(String[] args) {
        new MaxSubarrayProductLen().getMaxLen(new int[]{-1,-2,-3,0,1});
    }
}
